import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/27 16:07
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] graph = {{1,2},{2,3},{5}, {0}, {5}, {}, {}};
        solution.eventualSafeNodes(graph);
    }
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        TreeSet<Integer> treeSet = new TreeSet<>();
        // 三色标记法，0代表节点尚未访问，1代表节点位于递归栈或环中，2代表访问结束还是安全节点
        int[] color = new int[n];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (safe(graph, color, i)) {
                ans.add(i);
            }
        }
        return ans;
    }

    /**
     * 查询节点是否为安全节点
     * @param graph 图
     * @param color 节点状态颜色
     * @param i 当前节点
     * @return true or false
     */
    public boolean safe(int[][] graph, int[] color, int i) {
        if (color[i] > 0) {
            // 访问过，返回是陷入循环还是安全节点
            return color[i] == 2;
        }
        // 先置为1，代表在循环中
        color[i] = 1;
        for (int y : graph[i]) {
            if(!safe(graph, color, y)) {
                return false;
            }
        }
        // i节点的所有路径都没有到环，设置为2
        color[i] = 2;
        return true;
    }
}
